# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root:
            return TreeNode(val)
        p, q = None, root
        while q:
            if val > q.val:
                p = q
                q = q.right
            elif val <= q.val:
                p = q
                q = q.left
        if val > p.val:
            p.right = TreeNode(val)
        else:
            p.left = TreeNode(val)
        return root

